/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        in = inorder;
        pre = preorder;
        return recursive(0, preorder.size() - 1, 0, preorder.size() - 1);
    }
    TreeNode* recursive(int pre_begin, int pre_end, int in_begin, int in_end) {
        if(pre_begin > pre_end) return NULL;
        int index = distance(in.begin() + in_begin, find(in.begin() + in_begin, in.begin() + in_end, pre[pre_begin]));
        TreeNode* node = new TreeNode(pre[pre_begin]);
        node -> left = recursive(pre_begin + 1, pre_begin + index, in_begin, in_begin + index - 1);
        node -> right = recursive(pre_begin + index + 1, pre_end, in_begin + index + 1, in_end);
        return node;
    }
private:
    vector<int> pre, in;
};
